#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 3333. 找到初始输入字符串 II
// https://leetcode.cn/problems/find-the-original-typed-string-ii/description/?envType=daily-question&envId=2025-07-02

class Solution
{
    int mod = 1000000007;

public:
    long long recursionTry(vector<int> &freq, vector<vector<long long>> &dp, int curIndex, int k){
        if(k == 1 || curIndex == freq.size()){
            return 1;
        }
        if(dp[curIndex][k] != -1){
            return dp[curIndex][k];
        }
        long long sum = 0;
        for (int i = 0; i <= freq[curIndex] && k - i >= 1; i++)
        {
            sum = (sum + recursionTry(freq, dp,curIndex + 1, k - i)) % mod;
        }
        dp[curIndex][k] = sum;
        return sum;
    }
    int possibleStringCount(string word, int k)
    {
        int n = word.size();
        if (n < k)
        {
            return 0;
        }
        long long ans = 1;
        vector<int> freq;
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            ++cnt;
            if (i == n - 1 || word[i] != word[i + 1])
            {
                if (cnt > 1)
                {
                    freq.push_back(cnt - 1);
                    ans = (ans * cnt) % mod;
                }
                cnt = 0;
                k--;
            }
        }
        if (k <= 0)
        {
            return ans;
        }
        vector<vector<long long>> dp(freq.size(), vector<long long>(k + 1, -1));
        long long lessKCnt = recursionTry(freq, dp, 0, k);
        return ((ans + mod) - lessKCnt)%mod;
    }
};

int main()
{
    return 0;
}